package LeetCode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class LC_207_CourseSchedule {

    public static void main(String[] args) {

    }

    static class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            HashMap<Integer, List<Integer>> maps = new HashMap<>();
            int[] indegree = new int[numCourses];
            int length = prerequisites.length;
            if (length <= 0) return true;
            for (int[] prerequisite : prerequisites) {
                int first = prerequisite[0];
                int second = prerequisite[1];
                if (!maps.containsKey(first))
                    maps.put(first, new LinkedList<>());
                maps.get(first).add(second);
                indegree[second]++;
            }

            List<Integer> list = new LinkedList<>();
            for (int i = 0; i < numCourses; i++) {
                if (indegree[i] == 0)
                    list.add(i);
            }
            while (list.size() > 0) {
                int val = list.get(0);
                indegree[val] = -1;
                list.remove(0);
                if (!maps.containsKey(val)) continue;
                List<Integer> tmpList = maps.get(val);
                for (Integer aTmpList : tmpList) {
                    int index = aTmpList;
                    indegree[index]--;
                    if (indegree[index] == 0)
                        list.add(index);
                }
            }
            for (int i = 0; i < numCourses; i++)
                if (indegree[i] != -1)
                    return false;
            return true;
        }
    }

}